%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beamer Presentation
% LaTeX Template
% Version 1.0 (10/11/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND THEMES
%----------------------------------------------------------------------------------------

\documentclass{beamer}

\mode<presentation> {
\usetheme{Madrid} % very very good
}

\usepackage{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables
\usepackage{pgf,pgfpages}
\usepackage{units}
\usepackage{listings}
\usepackage[utf8]{inputenc}

\usepackage[variablett]{lmodern}

\lstset{ %
  backgroundcolor=\color{white},   % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
%  basicstyle=\footnotesize,        % the size of the fonts that are used for the code
  language=C++,
%  basicstyle=\ttfamily,
  basicstyle=\ttfamily\scriptsize,
  keywordstyle=\color{blue}\ttfamily,
  stringstyle=\color{red}\ttfamily,
  commentstyle=\color{darkgreen}\ttfamily,
  breaklines=true,
  columns=flexible,
  literate={_}{\textsmallunderscore}1,
%  gobble=4,
%  xleftmargin=\leftmargini, 
%  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  captionpos=b,                    % sets the caption-position to bottom
  commentstyle=\color{green},      % comment style
  deletekeywords={...},            % if you want to delete keywords from the given language
  extendedchars=true,              
  frame=single,                    % adds a frame around the code
  keepspaces=true,                 
  keywordstyle=\color{blue},       % keyword style
  morekeywords={*,function, foreach, procedure, put, pop, remove,...},
  numbers=left,                    % where to put the line-numbers; possible values are (none, left, right)
  numbersep=5pt,                   % how far the line-numbers are from the code
  numberstyle=\tiny\color{black}, % the style that is used for the line-numbers
  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
  showstringspaces=false,          % underline spaces within strings only
  stepnumber=1,                    % the step between two line-numbers. If it's 1, each line will be numbered
%  stringstyle=\color{mauve},    	% string literal style
%  tabsize=4,                       % sets default tabsize to 2 spaces 
  title=\lstname,                   % show the filename of files included with \lstinputlisting; also try caption instead of title
  mathescape=true
}



%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\title[Short title]{AbsCon} % The short title appears at the bottom of every slide, the full title is only on the title page
\author{
\vspace{0.2cm}
\vspace{0.2cm}
Etudiant: KHONG Minh Thanh \\
Superviseurs: Yves Deville, Jean-Baptiste Mairy
\vspace{0.4cm}
}

\institute{
Institut de la Francophonie pour l'Informatique \\
\& beCool Constraints Group, ICTEAM/INGI, UCL
}
\begin{document}

\begin{frame}
\titlepage % Print the title page as the first slide
\end{frame}

\begin{frame}
\frametitle{Overview} % Table of contents slide, comment this block out to remove it
\tableofcontents % Throughout your presentation, if you choose to use \section{} and \subsection{} commands, these will automatically be printed on this slide as an overview of your presentation
\end{frame}

%----------------------------------------------------------------------------------------
%	PRESENTATION SLIDES
%----------------------------------------------------------------------------------------

%------------------------------------------------
\section{Les paquets} % Sections can be created in order to organize your presentation into discrete blocks, all sections and subsections are automatically printed in the table of contents as an overview of the talk
%------------------------------------------------
\begin{frame}
\frametitle{Les paquets dans AbsCon}
Les paquets principaux dans AbsCon
\begin{itemize}
\item \textbf{\textit{abscon}} : pour lancer le programme, initialiser le problème, le solveur
\item \textbf{\textit{problem.*}} : contenir les classe pour présenter un problème, tous les problèmes doivent étendre la classe "Problem"
\item \textit{\textbf{variable}} : pour définir les variables du problème
\item \textbf{\textit{variable.domain}} : pour définir le domaine de variables
\item \textbf{\textit{contraint.*}} : pour représenter les contraintes
\item \textbf{\textit{search.*, heuristic.*}} : les heuristiques, les algorithmes pour la recherche
\item \textbf{\textit{propagation.*}} : pour la propagation, il y a plusieurs type de propagation : AC, FC, SAC, \dots
\end{itemize}
\end{frame}

%------------------------------------------------

%------------------------------------------------
\section{Comment résoudre un CSP}
%------------------------------------------------
\begin{frame}
\frametitle{Comment résoudre un CSP}
	\begin{figure}[ht]
		\includegraphics[height=6.5cm]{./images/absconResolution.png}
		\caption{AbsCon: Résolution d'un CSP \cite{AbsCon}}
	\end{figure}
\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Comment résoudre un CSP}
\begin{itemize}
\item \textbf{Solver} : se situe dans le paquet \textbf{search.*}
	\begin{itemize}
	\item Elle implémente l'algorithme DFS (Depth First Search) avec Backtracking.
	\item Quand le solveur "solver" est créé, un CSP est associé avec lui.
	\item Le solveur gère l’ensemble d'assignation et essaiment, à chaque pas faire une nouvelle assignation.
	\end{itemize}
\item \textbf{VariableChooser, ValueChooser} : se situent dans \textbf{heuristics.*} 
	\begin{itemize}
	\item Pour choisir la variable, la valeur à assigner dans chaque assignation.
	\end{itemize}
\item \textbf{Propagator} : se situe dans \textbf{propagation.*}
	\begin{itemize}
	\item Elle représente la méthode pour propagation, elle est liée avec la classe "Constraint" pour tester la consistance.
	\item AC, FC, GT, BT, \dots
	\end{itemize}
\end{itemize}
\end{frame}

%------------------------------------------------

%------------------------------------------------
\section{La propagation dans AbsCon}
%------------------------------------------------
\begin{frame}
\frametitle{La propagation dans AbsCon}
\begin{itemize}

\item Les paquets pour la propagation sont dans \textbf{Propagation.*}.

\item Quand la propagation est lancée : 
	\begin{itemize}
	\item Au départ :\\ \textbf{enforce() }
	\item Après chaque décision positive (assignation) :
	\textbf{enforceAfterAssignmentOf(Variable)}
	\item Après chaque décision negative (réfutation) :
	\textbf{enforceAfterRefutationOf(Variable)}
	\end{itemize}
\item La propagation est orientée variables, signifiant que la queue Q
utilisée pour la propagation contient des variables.
\item Quand une variable x est choisie dans Q, toutes les contraintes portant
sur x sont sollicitées pour filtrer (méthode \textit{Constraint.filterFrom(Variable)}).

\end{itemize}
\end{frame}

%------------------------------------------------
\begin{frame}[fragile]
\frametitle{La propagation dans AbsCon}
Ces méthodes précédentes appellent \textit{Propagation.propagate()} pour forcer la consistance.

\begin{lstlisting} [caption= méthode propagate()]
Propagation.propagate()
// OUT : reviser tous les variables dans la queue et enlever les inconsistances
  Prendre chaque variable $x$ dans la queue
    Pour chaque contrainte $c$ portant sur $x$
      Appeler $c.filter($x$)$
\end{lstlisting}

La méthode $c.filter(x)$ va réviser la consistance pour tous les variables dans $c$. Lorsqu'elle détecte l'inconsistance d'une valeur, cette valeur est enlevé et la variable est mise dans la queue.

\end{frame}

%------------------------------------------------


%------------------------------------------------
\section{AC}
%------------------------------------------------
\begin{frame}
\frametitle{AC}
La propagation AC est définir dans la classe "AC" sous le paquet \textbf{Propagation.*}. Elle étend la classe "Propagation". 

\begin{itemize}
\item \textit{enforce()} : 
	\begin{itemize}
	\item mettre tous les variables dans la queue
	\item propagate()
	\end{itemize}
\item \textit{enforceAfterAssiggmentOf(Variable)} :
	\begin{itemize}
	\item mettre cette variable dans la queue
	\item propagate()
	\end{itemize}
\item \textit{enforceAfterRefutationOf(Variable)} :
	\begin{itemize}
	\item mettre cette variable dans la queue
	\item propagate()
	\end{itemize}
\end{itemize}
\end{frame}

%------------------------------------------------


%------------------------------------------------
\section{SAC}
%------------------------------------------------
\begin{frame}
\frametitle{SAC}
\begin{itemize}

\item La classe \textit{SAC} étend la classe \textit{StrongConsistency} qui étend la classe \textit{AC}. Elle est dans le paquet \textbf{propagation.*}.

\item L'idée de StrongConsistency est d'ajouter la méthode \textit{enforceMore()} dans les méthodes \textit{enforce(), enforceAfterAssiggmentOf(Variable), enforceAfterRefutationOf(Variable)}.

\item La méthode \textit{enforeMore()} va examiner la consistance pour chaque future variable par la méthode \textit{makeSingletonTestOn(Variable)} dans la classe SAC.

\item La méthode \textit{makeSingletonTestOn(Variable)} teste pour chaque valeur d'une variable le SAC, l'enlever si elle ne satisfait pas.

\item Arrêter quand il y a pas de changement, quand il y a le changement, redémarrer enforceMore()
\end{itemize}
\end{frame}

%------------------------------------------------


%------------------------------------------------
\section{MaxRPWC}
%------------------------------------------------
\begin{frame}
\frametitle{MaxRPWC}
\begin{itemize}
\item L'algorithme MaxRPWC est implémenter par deux classes : \textit{MaxRPWC} et \textit{ConstraintHardExtensionRPWC}.

\item La classe \textit{MaxRPWC} étend la classe \textit{AC}. Quand la propagation \textit{MaxRPWC} est créée, elle va trouver les intersections entre les contrainte de type \textit{ConstraintHardExtensionRPWC} et les ajouter dans ces contraintes.

\item La classe \textit{ConstraintHardExtensionRPWC} implémente la méthode \textit{runPropagator(Variable)} qui est sollicitée pour la propagation.

\end{itemize}

\end{frame}

%------------------------------------------------

\begin{frame}[fragile]
\frametitle{MaxRPWC}
\textit{ConstraintHardExtensionRPWC.runPropagator(Variable)}
\begin{lstlisting} [caption= méthode runPropagator()]
ConstraintHardExtensionRPWC.runPropagator(Variable)
// OUT : enlever les tuples invalides, ne pas étendre aux autres tuples, 
//        les valeurs inconsistantes du domaine de variable
  Prendre les intersections a tester
     Pour chaque tuple $\tau$ dans les intersections
       Si $\tau$ est invalide ou $\tau$ ne peut pas etendre aux autres tuples
          Enlever $\tau$
     Mettre a jours le domaine des variables
\end{lstlisting}
\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{References}
\footnotesize{
\begin{thebibliography}{99} % Beamer does not support BibTeX so references must be inserted manually as below
\bibitem{AbsCon} Merchez, Sylvain, Christophe Lecoutre, and Frédéric Boussemart. "Abscon: A prototype to solve csps with abstraction." Principles and Practice of Constraint Programming—CP 2001. Springer Berlin Heidelberg, 2001.
\end{thebibliography}
}
\end{frame}

%------------------------------------------------

\begin{frame}
\Huge{\centerline{The End}}
\end{frame}

%----------------------------------------------------------------------------------------

\end{document} 